// @FileName  :solve.c
// @Time      :2024/3/28 20:46
// @Author    :YKW
//# include <bits/stdc++.h>
//using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma once
#pragma pack (16)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("abm,avx,avx2,f16c,fma,mmx,popcnt,sse,sse2,sse3,sse4,ssse3,tune=native")

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <ctype.h>

# define isalpha(a) ((( (a>='a') && (a<='z') ) || ((a>='A') && (a<='Z'))) ? (1):(0))
# define isdigit(a) (((a<='9')&&(a>='0')) ? (1):(0))
# define isalnum(a) ((isdigit(a) || isalpha(a)) ? (1):(0))

# define HashLen (26*26*26)
# define max2(a, b) ((a)>(b)?(a):(b))
# define min2(a, b) ((a)<(b)?(a):(b))
# define min3(a, b, c) (min2(a,min2(b,c)))
# define maxLen 8192
# define numOfProgram 300
# define numOfFunc 50
int **Dp, MaxDP = 3300;                                //for dynamic programming

static inline void error2(char *s) {
    fprintf(stderr, "%s\n", s);
    exit(-1);
}

static inline void initDP() {
    int i;
    Dp = (int **) malloc(MaxDP * sizeof(int *));
    for (i = 0; i < MaxDP; i++)
        Dp[i] = (int *) malloc(MaxDP * sizeof(int));
}

static inline int editdistDP(char *str1, char *str2) {
    int i, j;
    int len1, len2;
    static int flag = 0;

    (flag++) ? Dp : initDP();
    len1 = strlen(str1) + 1;
    len2 = strlen(str2) + 1;
    (max2(len1, len2) >= MaxDP) ? error2("DP memory error!") : len1;
#pragma omp parallel for
    for (i = 0; i <= len1; i++) {
#pragma omp parallel for
        for (j = 0; j <= len2; j++) {
            if (i == 0)
                Dp[i][j] = j;
            else if (j == 0)
                Dp[i][j] = i;
            else if (str1[i - 1] == str2[j - 1])
                Dp[i][j] = Dp[i - 1][j - 1];
            else
                Dp[i][j] = 1 + min3(Dp[i][j - 1], Dp[i - 1][j], Dp[i - 1][j - 1]);
        }
    }
    return Dp[len1][len2];
}


struct node {//keepwords
    char data[10];
    struct node *next;
} ;
struct Title {
    char tt[64];
    int index, id;
} title[numOfProgram][numOfFunc];//(ind,函数号)->名称
struct cached {
    char id[32];
    struct cached *nxt;
} *ans[numOfProgram];
char kw[200][10] = {"auto",
                    "double",
                    "int",
                    "struct",
                    "break",
                    "else",
                    "long",
                    "switch",
                    "case",
                    "enum",
                    "register",
                    "typedef",
                    "char",
                    "extern",
                    "return",
                    "union",
                    "const",
                    "float",
                    "short",
                    "unsigned",
                    "continue",
                    "for",
                    "signed",
                    "void",
                    "default",
                    "goto",
                    "sizeof",
                    "volatile",
                    "do",
                    "if",
                    "while",
                    "static",
                    "fopen",
                    "freopen",
                    "fflush",
                    "fclose",
                    "remove",
                    "rename",
                    "tmpfile",
                    "tmpnam",
                    "setvbuf",
                    "setbuf",
                    "fprintf",
                    "printf",
                    "sprintf",
                    "fscanf",
                    "scanf",
                    "sscanf",
                    "fgetc",
                    "fgets",
                    "fputc",
                    "fputs",
                    "getc",
                    "getchar",
                    "gets",
                    "putc",
                    "putchar",
                    "puts",
                    "ungetc",
                    "fread",
                    "fwrite",
                    "fseek",
                    "ftell",
                    "rewind",
                    "fgetpos",
                    "fsetpos",
                    "clearerr",
                    "feof",
                    "ferror",
                    "perror",
                    "isalnum",
                    "isalpha",
                    "iscntrl",
                    "isdigit",
                    "isgraph",
                    "islower",
                    "isprint",
                    "ispunct",
                    "isspace",
                    "isupper",
                    "isxdigit",
                    "tolower",
                    "toupper",
                    "strcpy",
                    "strncpy",
                    "strcat",
                    "strncat",
                    "strcmp",
                    "strncmp",
                    "strchr",
                    "strrchr",
                    "strapn",
                    "strcapn",
                    "strpbrk",
                    "strstr",
                    "strlen",
                    "strerror",
                    "strtok",
                    "memcpy",
                    "memmove",
                    "memcmp",
                    "memchr",
                    "memset",
                    "sin",
                    "cos",
                    "tan",
                    "asin",
                    "acos",
                    "atan",
                    "atan2",
                    "sinh",
                    "cosh",
                    "tanh",
                    "exp",
                    "log",
                    "log10",
                    "pow",
                    "sqrt",
                    "ceil",
                    "floor",
                    "fabs",
                    "ldexp",
                    "frexp",
                    "modf",
                    "fmod",
                    "atof",
                    "atoi",
                    "atol",
                    "strtod",
                    "strtol",
                    "strtoul",
                    "rand",
                    "srand",
                    "calloc",
                    "malloc",
                    "realloc",
                    "free",
                    "abort",
                    "exit",
                    "atexit",
                    "system",
                    "getenv",
                    "bsearch",
                    "qsort",
                    "abs",
                    "labs",
                    "div",
                    "ldiv",
                    "assert",
                    "va_start",
                    "va_arg",
                    "va_end",
                    "setjmp",
                    "longjmp",
                    "signal",
                    "raise",
                    "clock",
                    "time",
                    "difftime",
                    "mktime",
                    "asctime",
                    "ctime",
                    "gmtime",
                    "localtime",
                    "strftime",
                    "func"};
struct node *hashTable[HashLen];//首字母*26+尾字母 的hash表 0表示keepwords 其他的表示第n个的函数保留字符
char rawContent[numOfProgram][numOfFunc][maxLen];//每段代码的(ind,函数号)->内容
char processedContent[numOfProgram][maxLen];//每段代码的(ind)->debuginfo
char id[numOfProgram][numOfFunc];//每条程序的编号
int ind, left, vised[numOfProgram], numOfFun[numOfProgram], numOfMain[numOfProgram], ans_count;//ind:第n[1-n]个程序  左大括号数量  该条是否超出阈值   每个main的函数量
int isId;

int cmp(const void *a, const void *b) {
    struct Title *p = (struct Title *) a, *q = (struct Title *) b;
    return p->index - q->index;//升序
}

int cmp_len(const void *a, const void *b) {
    struct Title *p = (struct Title *) a, *q = (struct Title *) b;
    return strlen(q->tt) - strlen((p->tt));//升序
}

static inline  int findWord(char *word) {
    if (ispunct(*word)) return 0;
    register int res = 0;
    struct node *p = hashTable[(word[0] - 'a') * 26 + word[1] - 'a'];
    while (p != NULL) {
        if (strcmp(p->data, word) == 0) {
            res = 1;
            break;
        }
        p = p->next;
    }
    return res;
}

static inline  int isNum(char *ch) {
#pragma omp parallel for
    for (int i = 0; i < strlen(ch); i++)
        if (*(ch + i) > '9' || *(ch + i) < '0') return 0;
    return 1;
}

static inline  char *getWord(char *word) {
    register char *res, *p = (char *) malloc(sizeof(char) * 20);
    res = p;
    if (ispunct(*word) && (*word != '_')) //获取一堆符号符号
        while (ispunct(*word) && (*word != '_'))*p++ = *word, word++;
    else if (isalnum(*word) || (*word == '_')) //获取一个变量/函数名
        while (isalnum(*word) || (*word == '_'))*p++ = *word, word++;
    else
        while (!(ispunct(*word) || isalnum(*word)) && strlen(word) > 0)word++;
    *p = '\0';
    return res;
}

// 在字符串数组中替换字符串的函数
static inline void replaceInString(char *arr, const char *oldStr, const char *newStr) {
    register char *tmp = arr;  // 保存原始指针，以便稍后释放（如果需要）
    size_t oldLen = strlen(oldStr);
    size_t newLen = strlen(newStr);
    size_t len = strlen(tmp);
    // 替换字符串
    register char *pos = strstr(tmp, oldStr);
    while (pos) {
        memmove(pos + newLen, pos + oldLen, len - (pos - tmp) - oldLen + 1);
        memcpy(pos, newStr, newLen);
        len += newLen - oldLen;  // 更新字符串长度（仅用于检查下一个替换）
        pos = strstr(pos + newLen, oldStr);
    }
}

int main() {
//    setbuf(stdout, NULL);
//buildHash
#pragma omp parallel for
    for (int i = 0; i < HashLen; i++)
        hashTable[i] = (struct node *) malloc(sizeof(struct node)), hashTable[i]->next = NULL;
#pragma omp parallel for
    for (int i = 0; i <= 165; i++) {
        int hashKey = (kw[i][0] - 'a') * 26 + kw[i][1] - 'a';
        struct node *tmp = hashTable[hashKey];
        while (tmp->next != NULL)
            tmp = tmp->next;
        tmp->next = (struct node *) malloc(sizeof(struct node));
        strcpy(tmp->next->data, kw[i]);
        tmp->next->next = NULL;
    }

//get debugInfo
    char *line = (char *) malloc(sizeof(char) * 256);
    char *con = (char *) malloc(sizeof(char) * 5200);
    FILE *codes = fopen("codes.txt", "rb");
    memset(con, 0, strlen(con));

//while获取原始程序，并分割
    while (fgets(line, 256, codes) != NULL) {
        if (strlen(line) < 1)continue;
        isId = 0;
        char *p = line;
        while (*p != '\r' && *p != '\n' && *p != '\t') {
            if (!isdigit(*p)) {
                p = line;
                break;
            }
            p++;
        }
        isId = (p == line) ? 0 : 1;
        if (isId) {//程序编号
//            rawContent[ind][numOfFun[ind] - 1] = (char *) malloc(sizeof(char) * strlen(con) << 2);
            strcpy(rawContent[ind][numOfFun[ind] - 1], con); //缓存区放到上个程序的最后一个函数
            memset(con, 0, strlen(con));
            strcpy(id[++ind], getWord(line));
            continue;
        }
        if (left == 0 && isalpha(line[0])) { //读到下一个函数名，把缓存区粘到上一个函数的位置
            char *tmp = line + strlen(line);
            int right = 0;
            while (*tmp != ')')tmp--;
#pragma omp parallel for
            for (int cnt = 0; cnt < strlen(line); cnt++) {
                if (line[cnt] == '{')left++;
                else if (line[cnt] == '}')right++;
            }

            char *ptr = strtok(line, "(");
            if (numOfFun[ind] != 0) {//不能粘在当前，上面已经把缓存区粘到上一个里面
//                rawContent[ind][numOfFun[ind] - 1] = (char *) malloc(sizeof(char) * strlen(con) << 2);
                strcpy(rawContent[ind][numOfFun[ind] - 1], con);
            }
            memset(con, 0, strlen(con));
            if (*tmp == ')')strcat(con, tmp + 1);
            strcat(title[ind][numOfFun[ind]].tt, ptr);
            strcat(title[ind][numOfFun[ind]].tt, "("); //粘个左括号
            left -= right;

            if (strcmp(title[ind][numOfFun[ind]].tt, "main(") == 0)
                numOfMain[ind] = numOfFun[ind];
            title[ind][numOfFun[ind]].id = numOfFun[ind];
            numOfFun[ind]++;
            continue;
        }
#pragma omp parallel for
        for (register int cnt = 0; cnt < strlen(line); cnt++) {
            if (*(line + cnt) == '{')left++;
            else if (*(line + cnt) == '}')left--;
        }
        strcat(con, line);//先读入原始
    }
    numOfFun[ind]--;
//    rawContent[ind][numOfFun[ind]] = (char *) malloc(sizeof(char) * strlen(con) << 2);
    strcpy(rawContent[ind][numOfFun[ind]++], con);
    //处理并拼接程序
#pragma omp parallel for
    for (register int i = 1; i <= ind; i++) {//处理ind=i号程序
        int cnt = 0;
        int len = strlen(rawContent[i][numOfMain[i]]);
        char *pos;
        memset(con, 0, strlen(con));
        //按调用序号排序,不需要考虑main函数排序
#pragma omp parallel for
        for (int j = 0; j < numOfFun[i]; j++, cnt++) {
            if (strcmp(title[i][j].tt, "main(") == 0)
                title[i][j].index = 0;
            else if ((pos = strstr(rawContent[i][numOfMain[i]], title[i][j].tt)) != NULL) {
                title[i][j].index = pos - rawContent[i][numOfMain[i]];
            } else
                title[i][j].index = len, cnt--;
        }
        qsort(title[i], numOfFun[i], sizeof(struct Title), cmp_len);

        //替换第j个函数函数内部函数名为func (按出现序号
#pragma omp parallel for
        for (register int j = 0; j < numOfFun[i]; j++) {
            //替换函数名
#pragma omp parallel for
            for (register int k = 0; strlen(title[i][k].tt) > 0; k++) {//不需要替换main
                while ((strstr(rawContent[i][title[i][j].id], title[i][k].tt)) != NULL)
                    replaceInString(rawContent[i][title[i][j].id], title[i][k].tt, "func(");
            }
        }
        qsort(title[i], numOfFun[i], sizeof(struct Title), cmp);

        //拼接第j个函数函数(按调用序号
#pragma omp parallel for
        for (int j = 0; j < cnt; j++) {
            //把同一个程序的所有函数处理并拼接
#pragma omp parallel for
            for (char *word = strtok(rawContent[i][title[i][j].id], "\t\r\n ");
                 word != NULL; word = strtok(NULL, "\t\r\n ")) {
                char *p = word;
                while (strlen(p) > 0) {
                    char *wword = getWord(p);
                    if (strlen(wword) == 0)break;
                    p += strlen(wword);
                    if (findWord(wword) == 1 || (ispunct(wword[0]) && wword[0] != '_') || isNum(wword))
                        strcat(con, wword);
                }
            }
        }
//        processedContent[i] = (char *) malloc(sizeof(char) * strlen(con) << 2);
        strcpy(processedContent[i], con);
//        printf("%s\n", id[i]);
//        printf("%s\n\n", processedContent[i]);
    }
    //计算相似度
#pragma omp parallel for
    for (register int i = 1; i < ind; i++) {
        int flag = 0;//是否加入
        if (vised[i]) continue;
#pragma omp parallel for
        for (register int j = i + 1; j <= ind; j++) {
            double len = max2(strlen(processedContent[i]), strlen(processedContent[j]));
            double sim = 1 - (double) editdistDP(processedContent[i], processedContent[j]) / len;
            if (sim > 0.95) {
                vised[j] = 1;
                if (ans[ans_count] != NULL && strcmp(ans[ans_count]->id, id[i]) == 0) {//已经有记录
                    struct cached *neo = (struct cached *) malloc(sizeof(struct cached)), *p = ans[ans_count];
                    strcpy(neo->id, id[j]);
                    neo->nxt = NULL;
                    while (p->nxt != NULL)
                        p = p->nxt;
                    p->nxt = neo;
                } else {
                    ans[ans_count] = (struct cached *) malloc(sizeof(struct cached));
                    strcpy(ans[ans_count]->id, id[i]);
                    struct cached *neo = (struct cached *) malloc(sizeof(struct cached)), *p = ans[ans_count];
                    strcpy(neo->id, id[j]);
                    neo->nxt = NULL;
                    p->nxt = neo;
                    flag = 1;
                }
            }
        }
        if (flag) ans_count++;
    }
#pragma omp parallel for
    for (register int i = 0; i < ans_count; i++) {
        struct cached *p = ans[i];
        while (p != NULL) {
            printf("%s ", p->id);
            p = p->nxt;
        }
        printf("\n");
    }
}
